Người Minangkabau từ Sumatra định cư tại Negeri Sembilan trong thế kỷ 14 dưới sự bảo trợ của Vương quốc Malacca, sau đó nằm dưới sự bảo trợ của quốc gia kế thừa là Vương quốc Johor. Negeri Sembilan là bang duy nhất tại Malaysia thực hành phong tục mẫu hệ vốn được người Minangkabau đưa đến. Do Johor suy yếu trong thế kỷ 18, các cuộc tấn công của người Bugis buộc người Minangkabau phải tìm cách bảo vệ quê hương mình. Quân chủ người Minangkabau tại Sumatra là Sultan Abdul Jalil buộc phải phái một người họ hàng là Raja Melewar đến khu vực. Khi Raja Melewar đến, ông ta phát hiện Raja Khatib đã tự lập làm quân chủ. Raja Melewar tuyên chiến chống Raja Khatib và trở thành quân chủ đầu tiên của Negeri Sembilan. Sultan của Johor xác nhận vị thế của Raja Melewar bằng việc ban tước hiệu Yang di-Pertuan Besar Negeri Sembilan vào năm 1773. Sau khi Raja Melewar từ trần, một loạt tranh chấp nổi lên quanh vấn đề kế vị, thường dẫn đến bất ổn và nội chiến.

Năm 1873, người Anh can thiệp quân sự trong nội chiến tại Sungai Ujong nhằm đảm bảo lợi ích kinh tế của Anh, và đặt quốc gia này dưới quyền kiểm soát của một Công sứ Anh. Điều tương tự diễn ra với Jelebu vào năm 1886, và với các quốc gia còn lại vào năm 1895. Năm 1897, khi Các quốc gia Mã Lai Liên hiệp được thành lập, Sungai Ujong và Jelebu được hợp nhất trong một liên minh của các tiểu quốc và được gọi với tên cũ là Negeri Sembilan, đặt dưới quyền kiểm soát của một Công sứ duy nhất và trở thành một thành viên của Các quốc gia Mã Lai Liên hiệp.

Số lượng tiểu quốc trong Negeri Sembilan dao động theo thời gian, từng phải nhượng Naning cho Malacca, Kelang cho Selangor, và Segamat cho Johor.

Negeri Sembilan bị Nhật Bản chiếm đóng trong Chiến tranh thế giới thứ hai, từ 1942 đến 1945, và gia nhập Liên bang Malaya vào năm 1948, và trở thành một bang của Malaysia vào năm 1963.